
%% bare_jrnl_compsoc.tex
%% V1.4
%% 2012/12/27
%% by Michael Shell
%% See:
%% http://www.michaelshell.org/
%% for current contact information.
%%
%% This is a skeleton file demonstrating the use of IEEEtran.cls
%% (requires IEEEtran.cls version 1.8 or later) with an IEEE Computer
%% Society journal paper.
%%
%% Support sites:
%% http://www.michaelshell.org/tex/ieeetran/
%% http://www.ctan.org/tex-archive/macros/latex/contrib/IEEEtran/
%% and
%% http://www.ieee.org/

%%*************************************************************************
%% Legal Notice:
%% This code is offered as-is without any warranty either expressed or
%% implied; without even the implied warranty of MERCHANTABILITY or
%% FITNESS FOR A PARTICULAR PURPOSE! 
%% User assumes all risk.
%% In no event shall IEEE or any contributor to this code be liable for
%% any damages or losses, including, but not limited to, incidental,
%% consequential, or any other damages, resulting from the use or misuse
%% of any information contained here.
%%
%% All comments are the opinions of their respective authors and are not
%% necessarily endorsed by the IEEE.
%%
%% This work is distributed under the LaTeX Project Public License (LPPL)
%% ( http://www.latex-project.org/ ) version 1.3, and may be freely used,
%% distributed and modified. A copy of the LPPL, version 1.3, is included
%% in the base LaTeX documentation of all distributions of LaTeX released
%% 2003/12/01 or later.
%% Retain all contribution notices and credits.
%% ** Modified files should be clearly indicated as such, including  **
%% ** renaming them and changing author support contact information. **
%%
%% File list of work: IEEEtran.cls, IEEEtran_HOWTO.pdf, bare_adv.tex,
%%                    bare_conf.tex, bare_jrnl.tex, bare_jrnl_compsoc.tex,
%%                    bare_jrnl_transmag.tex
%%*************************************************************************

% *** Authors should verify (and, if needed, correct) their LaTeX system  ***
% *** with the testflow diagnostic prior to trusting their LaTeX platform ***
% *** with production work. IEEE's font choices can trigger bugs that do  ***
% *** not appear when using other class files.                            ***
% The testflow support page is at:
% http://www.michaelshell.org/tex/testflow/




% Note that the a4paper option is mainly intended so that authors in
% countries using A4 can easily print to A4 and see how their papers will
% look in print - the typesetting of the document will not typically be
% affected with changes in paper size (but the bottom and side margins will).
% Use the testflow package mentioned above to verify correct handling of
% both paper sizes by the user's LaTeX system.
%
% Also note that the "draftcls" or "draftclsnofoot", not "draft", option
% should be used if it is desired that the figures are to be displayed in
% draft mode.
%
% The Computer Society usually requires 12pt for submissions.
%
\documentclass[12pt,journal,compsoc]{IEEEtran}
%
% If IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it like:
% \documentclass[12pt,journal,compsoc]{../sty/IEEEtran}





% Some very useful LaTeX packages include:
% (uncomment the ones you want to load)


% *** MISC UTILITY PACKAGES ***
%
%\usepackage{ifpdf}
% Heiko Oberdiek's ifpdf.sty is very useful if you need conditional
% compilation based on whether the output is pdf or dvi.
% usage:
% \ifpdf
%   % pdf code
% \else
%   % dvi code
% \fi
% The latest version of ifpdf.sty can be obtained from:
% http://www.ctan.org/tex-archive/macros/latex/contrib/oberdiek/
% Also, note that IEEEtran.cls V1.7 and later provides a builtin
% \ifCLASSINFOpdf conditional that works the same way.
% When switching from latex to pdflatex and vice-versa, the compiler may
% have to be run twice to clear warning/error messages.






% *** CITATION PACKAGES ***
%
\ifCLASSOPTIONcompsoc
  % IEEE Computer Society needs nocompress option
  % requires cite.sty v4.0 or later (November 2003)
  % \usepackage[nocompress]{cite}
\else
  % normal IEEE
  % \usepackage{cite}
\fi
% cite.sty was written by Donald Arseneau
% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
% \cite{} output to follow that of IEEE. Loading the cite package will
% result in citation numbers being automatically sorted and properly
% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
% \cite will automatically add leading space, if needed. Use cite.sty's
% noadjust option (cite.sty V3.8 and later) if you want to turn this off
% such as if a citation ever needs to be enclosed in parenthesis.
% cite.sty is already installed on most LaTeX systems. Be sure and use
% version 4.0 (2003-05-27) and later if using hyperref.sty. cite.sty does
% not currently provide for hyperlinked citations.
% The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/cite/
% The documentation is contained in the cite.sty file itself.
%
% Note that some packages require special options to format as the Computer
% Society requires. In particular, Computer Society  papers do not use
% compressed citation ranges as is done in typical IEEE papers
% (e.g., [1]-[4]). Instead, they list every citation separately in order
% (e.g., [1], [2], [3], [4]). To get the latter we need to load the cite
% package with the nocompress option which is supported by cite.sty v4.0
% and later. Note also the use of a CLASSOPTION conditional provided by
% IEEEtran.cls V1.7 and later.





% *** GRAPHICS RELATED PACKAGES ***
%
\ifCLASSINFOpdf
  \usepackage[pdftex]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../pdf/}{../jpeg/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
\else
  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
  % will default to the driver specified in the system graphics.cfg if no
  % driver is specified.
  % \usepackage[dvips]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../eps/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.eps}
\fi
% graphicx was written by David Carlisle and Sebastian Rahtz. It is
% required if you want graphics, photos, etc. graphicx.sty is already
% installed on most LaTeX systems. The latest version and documentation
% can be obtained at: 
% http://www.ctan.org/tex-archive/macros/latex/required/graphics/
% Another good source of documentation is "Using Imported Graphics in
% LaTeX2e" by Keith Reckdahl which can be found at:
% http://www.ctan.org/tex-archive/info/epslatex/
%
% latex, and pdflatex in dvi mode, support graphics in encapsulated
% postscript (.eps) format. pdflatex in pdf mode supports graphics
% in .pdf, .jpeg, .png and .mps (metapost) formats. Users should ensure
% that all non-photo figures use a vector format (.eps, .pdf, .mps) and
% not a bitmapped formats (.jpeg, .png). IEEE frowns on bitmapped formats
% which can result in "jaggedy"/blurry rendering of lines and letters as
% well as large increases in file sizes.
%
% You can find documentation about the pdfTeX application at:
% http://www.tug.org/applications/pdftex






% *** MATH PACKAGES ***
%
\usepackage[cmex10]{amsmath}
% A popular package from the American Mathematical Society that provides
% many useful and powerful commands for dealing with mathematics. If using
% it, be sure to load this package with the cmex10 option to ensure that
% only type 1 fonts will utilized at all point sizes. Without this option,
% it is possible that some math symbols, particularly those within
% footnotes, will be rendered in bitmap form which will result in a
% document that can not be IEEE Xplore compliant!
%
% Also, note that the amsmath package sets \interdisplaylinepenalty to 10000
% thus preventing page breaks from occurring within multiline equations. Use:
%\interdisplaylinepenalty=2500
% after loading amsmath to restore such page breaks as IEEEtran.cls normally
% does. amsmath.sty is already installed on most LaTeX systems. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/amslatex/math/





% *** SPECIALIZED LIST PACKAGES ***
%
%\usepackage{algorithmic}
% algorithmic.sty was written by Peter Williams and Rogerio Brito.
% This package provides an algorithmic environment fo describing algorithms.
% You can use the algorithmic environment in-text or within a figure
% environment to provide for a floating algorithm. Do NOT use the algorithm
% floating environment provided by algorithm.sty (by the same authors) or
% algorithm2e.sty (by Christophe Fiorio) as IEEE does not use dedicated
% algorithm float types and packages that provide these will not provide
% correct IEEE style captions. The latest version and documentation of
% algorithmic.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithms/
% There is also a support site at:
% http://algorithms.berlios.de/index.html
% Also of interest may be the (relatively newer and more customizable)
% algorithmicx.sty package by Szasz Janos:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithmicx/




% *** ALIGNMENT PACKAGES ***
%
%\usepackage{array}
% Frank Mittelbach's and David Carlisle's array.sty patches and improves
% the standard LaTeX2e array and tabular environments to provide better
% appearance and additional user controls. As the default LaTeX2e table
% generation code is lacking to the point of almost being broken with
% respect to the quality of the end results, all users are strongly
% advised to use an enhanced (at the very least that provided by array.sty)
% set of table tools. array.sty is already installed on most systems. The
% latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/tools/


% IEEEtran contains the IEEEeqnarray family of commands that can be used to
% generate multiline equations as well as matrices, tables, etc., of high
% quality.




% *** SUBFIGURE PACKAGES ***
%\ifCLASSOPTIONcompsoc
%  \usepackage[caption=false,font=normalsize,labelfont=sf,textfont=sf]{subfig}
%\else
%  \usepackage[caption=false,font=footnotesize]{subfig}
%\fi
% subfig.sty, written by Steven Douglas Cochran, is the modern replacement
% for subfigure.sty, the latter of which is no longer maintained and is
% incompatible with some LaTeX packages including fixltx2e. However,
% subfig.sty requires and automatically loads Axel Sommerfeldt's caption.sty
% which will override IEEEtran.cls' handling of captions and this will result
% in non-IEEE style figure/table captions. To prevent this problem, be sure
% and invoke subfig.sty's "caption=false" package option (available since
% subfig.sty version 1.3, 2005/06/28) as this is will preserve IEEEtran.cls
% handling of captions.
% Note that the Computer Society format requires a larger sans serif font
% than the serif footnote size font used in traditional IEEE formatting
% and thus the need to invoke different subfig.sty package options depending
% on whether compsoc mode has been enabled.
%
% The latest version and documentation of subfig.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/subfig/




% *** FLOAT PACKAGES ***
%
%\usepackage{fixltx2e}
% fixltx2e, the successor to the earlier fix2col.sty, was written by
% Frank Mittelbach and David Carlisle. This package corrects a few problems
% in the LaTeX2e kernel, the most notable of which is that in current
% LaTeX2e releases, the ordering of single and double column floats is not
% guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
% single column figure to be placed prior to an earlier double column
% figure. The latest version and documentation can be found at:
% http://www.ctan.org/tex-archive/macros/latex/base/


%\usepackage{stfloats}
% stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
% the ability to do double column floats at the bottom of the page as well
% as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
% LaTeX2e). It also provides a command:
%\fnbelowfloat
% to enable the placement of footnotes below bottom floats (the standard
% LaTeX2e kernel puts them above bottom floats). This is an invasive package
% which rewrites many portions of the LaTeX2e float routines. It may not work
% with other packages that modify the LaTeX2e float routines. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/sttools/
% Do not use the stfloats baselinefloat ability as IEEE does not allow
% \baselineskip to stretch. Authors submitting work to the IEEE should note
% that IEEE rarely uses double column equations and that authors should try
% to avoid such use. Do not be tempted to use the cuted.sty or midfloat.sty
% packages (also by Sigitas Tolusis) as IEEE does not format its papers in
% such ways.
% Do not attempt to use stfloats with fixltx2e as they are incompatible.
% Instead, use Morten Hogholm'a dblfloatfix which combines the features
% of both fixltx2e and stfloats:
%
% \usepackage{dblfloatfix}
% The latest version can be found at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/dblfloatfix/




%\ifCLASSOPTIONcaptionsoff
%  \usepackage[nomarkers]{endfloat}
% \let\MYoriglatexcaption\caption
% \renewcommand{\caption}[2][\relax]{\MYoriglatexcaption[#2]{#2}}
%\fi
% endfloat.sty was written by James Darrell McCauley, Jeff Goldberg and 
% Axel Sommerfeldt. This package may be useful when used in conjunction with 
% IEEEtran.cls'  captionsoff option. Some IEEE journals/societies require that
% submissions have lists of figures/tables at the end of the paper and that
% figures/tables without any captions are placed on a page by themselves at
% the end of the document. If needed, the draftcls IEEEtran class option or
% \CLASSINPUTbaselinestretch interface can be used to increase the line
% spacing as well. Be sure and use the nomarkers option of endfloat to
% prevent endfloat from "marking" where the figures would have been placed
% in the text. The two hack lines of code above are a slight modification of
% that suggested by in the endfloat docs (section 8.4.1) to ensure that
% the full captions always appear in the list of figures/tables - even if
% the user used the short optional argument of \caption[]{}.
% IEEE papers do not typically make use of \caption[]'s optional argument,
% so this should not be an issue. A similar trick can be used to disable
% captions of packages such as subfig.sty that lack options to turn off
% the subcaptions:
% For subfig.sty:
% \let\MYorigsubfloat\subfloat
% \renewcommand{\subfloat}[2][\relax]{\MYorigsubfloat[]{#2}}
% However, the above trick will not work if both optional arguments of
% the \subfloat command are used. Furthermore, there needs to be a
% description of each subfigure *somewhere* and endfloat does not add
% subfigure captions to its list of figures. Thus, the best approach is to
% avoid the use of subfigure captions (many IEEE journals avoid them anyway)
% and instead reference/explain all the subfigures within the main caption.
% The latest version of endfloat.sty and its documentation can obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/endfloat/
%
% The IEEEtran \ifCLASSOPTIONcaptionsoff conditional can also be used
% later in the document, say, to conditionally put the References on a 
% page by themselves.




% *** PDF, URL AND HYPERLINK PACKAGES ***
%
%\usepackage{url}
% url.sty was written by Donald Arseneau. It provides better support for
% handling and breaking URLs. url.sty is already installed on most LaTeX
% systems. The latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/url/
% Basically, \url{my_url_here}.





% *** Do not adjust lengths that control margins, column widths, etc. ***
% *** Do not use packages that alter fonts (such as pslatex).         ***
% There should be no need to do such things with IEEEtran.cls V1.6 and later.
% (Unless specifically asked to do so by the journal or conference you plan
% to submit to, of course. )


% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}


\begin{document}
%
% paper title
% can use linebreaks \\ within to get better formatting as desired
% Do not put math or special symbols in the title.
\title{Fixed-Width Truncated Multipliers \\ Survey, Implementation and Proposal}
%
%
% author names and IEEE memberships
% note positions of commas and nonbreaking spaces ( ~ ) LaTeX will not break
% a structure at a ~ so this keeps an author's name from being broken across
% two lines.
% use \thanks{} to gain access to the first footnote area
% a separate \thanks must be used for each paragraph as LaTeX2e's \thanks
% was not built to handle multiple paragraphs
%
%
%\IEEEcompsocitemizethanks is a special \thanks that produces the bulleted
% lists the Computer Society journals use for "first footnote" author
% affiliations. Use \IEEEcompsocthanksitem which works much like \item
% for each affiliation group. When not in compsoc mode,
% \IEEEcompsocitemizethanks becomes like \thanks and
% \IEEEcompsocthanksitem becomes a line break with idention. This
% facilitates dual compilation, although admittedly the differences in the
% desired content of \author between the different types of papers makes a
% one-size-fits-all approach a daunting prospect. For instance, compsoc 
% journal papers have the author affiliations above the "Manuscript
% received ..."  text while in non-compsoc journals this is reversed. Sigh.

\author{Tuan~Nguyen\\Electrical and Computer Engineering\\
Oklahoma State University\\tuan.d.nguyen@okstate.edu}% <-this % stops a space
%\IEEEcompsocitemizethanks{\IEEEcompsocthanksitem M. Shell is with the Department
%of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta,
%GA, 30332.\protect\\
%% note need leading \protect in front of \\ to get a newline within \thanks as
%% \\ is fragile and will error, could use \hfil\break instead.
%E-mail: see http://www.michaelshell.org/contact.html
%\IEEEcompsocthanksitem J. Doe and J. Doe are with Anonymous University.}% <-this % stops an unwanted space
%\thanks{Manuscript received April 19, 2005; revised December 27, 2012.}}

% note the % following the last \IEEEmembership and also \thanks - 
% these prevent an unwanted space from occurring between the last author name
% and the end of the author line. i.e., if you had this:
% 
% \author{....lastname \thanks{...} \thanks{...} }
%                     ^------------^------------^----Do not want these spaces!
%
% a space would be appended to the last name and could cause every name on that
% line to be shifted left slightly. This is one of those "LaTeX things". For
% instance, "\textbf{A} \textbf{B}" will typeset as "A B" not "AB". To get
% "AB" then you have to do: "\textbf{A}\textbf{B}"
% \thanks is no different in this regard, so shield the last } of each \thanks
% that ends a line with a % and do not let a space in before the next \thanks.
% Spaces after \IEEEmembership other than the last one are OK (and needed) as
% you are supposed to have spaces between the names. For what it is worth,
% this is a minor point as most people would not even notice if the said evil
% space somehow managed to creep in.



% The paper headers
\markboth{ECEN 6050 PRELIMINARY EXAM, January~2015}%
{Tuan Nguyen: Fixed-Width Truncated Multipliers: Survey, Implementation and Proposal}
% The only time the second header will appear is for the odd numbered pages
% after the title page when using the twoside option.
% 
% *** Note that you probably will NOT want to include the author's ***
% *** name in the headers of peer review papers.                   ***
% You can use \ifCLASSOPTIONpeerreview for conditional compilation here if
% you desire.



% The publisher's ID mark at the bottom of the page is less important with
% Computer Society journal papers as those publications place the marks
% outside of the main text columns and, therefore, unlike regular IEEE
% journals, the available text space is not reduced by their presence.
% If you want to put a publisher's ID mark on the page you can do it like
% this:
%\IEEEpubid{0000--0000/00\$00.00~\copyright~2012 IEEE}
% or like this to get the Computer Society new two part style.
%\IEEEpubid{\makebox[\columnwidth]{\hfill 0000--0000/00/\$00.00~\copyright~2012 IEEE}%
%\hspace{\columnsep}\makebox[\columnwidth]{Published by the IEEE Computer Society\hfill}}
% Remember, if you use this you must call \IEEEpubidadjcol in the second
% column for its text to clear the IEEEpubid mark (Computer Society jorunal
% papers don't need this extra clearance.)



% use for special paper notices
%\IEEEspecialpapernotice{(Invited Paper)}



% for Computer Society papers, we must declare the abstract and index terms
% PRIOR to the title within the \IEEEtitleabstractindextext IEEEtran
% command as these need to go into the title area created by \maketitle.
% As a general rule, do not put math, special symbols or citations
% in the abstract or keywords.
\IEEEtitleabstractindextext{%
\begin{abstract}
Fixed-Width Multipliers are the basic components in many Digital Signal Processing (DSP) systems. In many cases, where the primary concerns are performance, area and power dissipation and controlled errors are acceptable, Truncated Multipliers are the favorite choice. The basic idea underlying Truncated Multipliers is that a number of least significant columns of Partial Products (PPs) are truncated to reduce area and power dissipation as well as increase performance. In this article, various techniques related to Truncated Multipliers are discussed, compared and contrasted. Second, three key techniques are implemented in Matlab to have the insight in those methods. Finally, a new proposed approach and preliminary results come at the end.
\end{abstract}

% Note that keywords are not normally used for peerreview papers.
\begin{IEEEkeywords}
Truncated Multipliers, Fixed-Width, Minimax, Low-Power Design
\end{IEEEkeywords}}


% make the title area
\maketitle


% To allow for easy dual compilation without having to reenter the
% abstract/keywords data, the \IEEEtitleabstractindextext text will
% not be used in maketitle, but will appear (i.e., to be "transported")
% here as \IEEEdisplaynontitleabstractindextext when the compsoc 
% or transmag modes are not selected <OR> if conference mode is selected 
% - because all conference papers position the abstract like regular
% papers do.
\IEEEdisplaynontitleabstractindextext
% \IEEEdisplaynontitleabstractindextext has no effect when using
% compsoc or transmag under a non-conference mode.



% For peer review papers, you can put extra information on the cover
% page as needed:
% \ifCLASSOPTIONpeerreview
% \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
% \fi
%
% For peerreview papers, this IEEEtran command inserts a page break and
% creates the second title. It will be ignored for other modes.
\IEEEpeerreviewmaketitle



\section{Introduction}
% Computer Society journal papers do something a tad strange with the very
% first section heading (almost always called "Introduction"). They place it
% ABOVE the main text! IEEEtran.cls currently does not do this for you.
% However, You can achieve this effect by making LaTeX jump through some
% hoops via something like:
%
%\ifCLASSOPTIONcompsoc
%  \noindent\raisebox{2\baselineskip}[0pt][0pt]%
%  {\parbox{\columnwidth}{\section{Introduction}\label{sec:introduction}%
%  \global\everypar=\everypar}}%
%  \vspace{-1\baselineskip}\vspace{-\parskip}\par
%\else
%  \section{Introduction}\label{sec:introduction}\par
%\fi
%
% Admittedly, this is a hack and may well be fragile, but seems to do the
% trick for me. Note the need to keep any \label that may be used right
% after \section in the above as the hack puts \section within a raised box.



% The very first letter is a 2 line initial drop letter followed
% by the rest of the first word in caps (small caps for compsoc).
% 
% form to use if the first word consists of a single letter:
% \IEEEPARstart{A}{demo} file is ....
% 
% form to use if you need the single drop letter followed by
% normal text (unknown if ever used by IEEE):
% \IEEEPARstart{A}{}demo file is ....
% 
% Some journals put the first two words in caps:
% \IEEEPARstart{T}{his demo} file is ....
% 
% Here we have the typical use of a "T" for an initial drop letter
% and "HIS" in caps to complete the first word.
%\IEEEPARstart{T}{his} demo file is intended to serve as a ``starter file''
%for IEEE Computer Society journal papers produced under \LaTeX\ using
%IEEEtran.cls version 1.8 and later.
%% You must have at least 2 lines in the paragraph with the drop letter
%% (should never be an issue)
%I wish you the best of success.
%
%\hfill mds
% 
%\hfill December 27, 2012
%The importance of multipliers and its improvement
High-speed parallel multipliers are fundamental building blocks in digital signal processing (DSP) systems \cite{ma:1990}. In many cases, parallel multipliers contribute a large part of these systems. As a result, improvement in multipliers can lead to significant improvement in DSP systems. 

%Introduce about fixed-width multipliers and full multipliers
A typical case of multiplication in many DSP systems is the fixed-width (or single-precision) multiplication, where given multiplicand and multiplier are $n$ bits binary numbers, the output product is also the $n$ bits number (in the full-width or double-precision multiplication, the output is $2n$ bits number). Using the fixed-width number systems help avoid grown in word size, save area and are simpler than full-width number systems.

An obvious way to do fixed-width multiplication is using full-width multipliers and then rounding $2n$ bits full-width result to $n$ bits results (Non-Truncated Fixed-Width Multipliers). Figure \ref{fig:8x8full} shows an example of Non-Truncated Fixed-Width Multipliers with inputs are 8 bits binary numbers $A(a_1 a_2..a_8)$ and $B(b_1 b_2..b_8)$. With this method, first, all 64 Partial Products $a_i\cdot b_j$ are computed, and then added together to have $16$ bits full-width product $P(p_1 p_2..p_{15} p_{16})$. This product is finally rounded to get $8$ bits final output.

\begin{figure*}[hbtp]
\centering
\includegraphics[width=\textwidth]{imgs/8x8full.PNG}
\caption{Non-truncated Fixed-Width Multipliers}
\label{fig:8x8full}
\end{figure*}

%Introduce about truncated multipliers and its problems
Although Non-Truncated Fixed-Width Multipliers is the best in terms of errors, it requires to compute all $n^2$ PPs and then add them together, which make it worst in terms of performance, area and power dissipation criteria. In many modern DSP systems, the primary concerns are the power dissipation, area and performance and they can tolerate some small errors. We should notice here that even the Non-Truncated Fixed-Width Multipliers still have errors due to rounding steps. That is where Truncated Fixed-Width Multipliers come to the scene.

With truncated multiplication, only the $(n+k)$, with $k$ much smaller than $n$, most significant columns of the multiplication matrix are used to compute the product. The error produced by omitting the $(n-k)$ least significant columns and rounding the final result to n bits is estimated, and this estimate (named Correction Value) is added along with the $(n+k)$ most significant columns to produce the rounded product. Figure \ref{fig:8x8trunc} shows an example of Truncated Multipliers for $(n = 8, k = 2)$. It can be seen clearly in the example that $21$ PPs ($33\%$ total PPs) can be get rid of, which results in a significant improvement in area, power dissipation and performance. More impressively, with $(n = 32, k = 2)$, up to $45\%$ PPs are truncated. Although it introduced Correction Value, it can be shown later that the Correction Value length is short and hence, does not cost much.

%Introduce very briefly about various techniques' contribution
Since the Lim's landmark paper in 1992 \cite{lim:1992}, various techniques have been developed to help find Correction Values that reduce the errors due to truncation and rounding in Truncated Fixed-Width Multipliers \cite{schulte:1993}, \cite{king:1997},\cite{stine:2003}. These papers can be classified into two classes: Correction Constant Truncation (CCT) and Variable Correction Truncation (VCT). The CCT methods use just one Correction Value for all inputs while the VCT methods use different Correction Values based on each input set. These methods will be discussed, compared and contrasted in detail in following sections.

%Organization of the rest of paper
The rest of this paper is organized as follow: Section II discusses the state of the art in Fixed-Width Truncated Multipliers, Section III describes an implementation in Matlab of three key techniques among them. In Section IV, experimental results are shown with some comparison and discussion. Section V is the proposal for the new approach to Fixed-Width Truncated Multipliers which takes into account the uncertainty of the inputs. Some preliminary results are also included in this section . Finally, Section VI is the Conclusion and Future Works.
\begin{figure*}[hbtp]
\centering
\includegraphics[width=\textwidth]{imgs/8x8trunc.PNG}
\caption{Truncated Fixed-Width Multipliers}
\label{fig:8x8trunc}
\end{figure*}

%State of the art
\section{State-of-the-Art}
In Fixed-Width Multipliers, it is convenient to assume that inputs (multiplicand and multiplier) are $n$ bits unsigned binary number represented as following:
\[
A = \sum_{i=1}^{n}{a_i \cdot 2^{-i}} \hspace{1 cm} B = \sum_{j=1}^{n}{b_j \cdot 2^{-j}}\\
\]

The Non-Truncated Fixed-Width Multipliers simply uses the Full-Width Multipliers which computes all PPs $a_i \cdot b_j$ and add them together to get full-width product $Z$ ($Z$ is $2n$ bits number):

\[
Z = A \cdot B = \sum_{i=1}^{n}\sum_{j=1}^{n} (a_i \cdot b_j) \cdot 2 ^{-i-j} =  \sum_{k=1}^{2n} {\pi_k \cdot 2^{-k}}
\]

$Z$ then is rounded to $n$ bits $\hat{Z}$ final output as following:
\[
\hat{Z} = \frac{\left[ Z \cdot 2^n \right]}{2^n}
\]

in which $y = \left[x \right]$ is the rounding to nearest even function. The error of this method, resulted from the rounding operation, is computed by:
\[
E = \hat{Z} - Z =  \frac{\left[ Z \cdot 2^n \right]}{2^n} - Z
\]
It is not hard to see that the average error $E_{avg} = 0$ and the absolute error $|E| \le \frac{2^{-n}}{2} = \frac{ulp}{2}$ (ulp is \textit{unit of least precision}). Although this method is the best in terms of errors, it requires to compute all $n^2$ PPs and add $n^2$ PPs together, which makes it worst in terms of performance, area and power dissipation. That is where Truncated Fixed-Width Multipliers come to the scene.

With truncated multiplication, only the $(n+k)$, with $k$ much smaller than $n$, most significant columns of the multiplication matrix are used to compute the product:
\[
Z_{trunc} =  \sum_{i=1,j=1}^{i+j \le n+k}(a_i \cdot b_j) \cdot 2 ^{-i-j}
\]
(Notice that column $m$ is the set of all PPs $a_i \cdot b_j$ such that $i+j = m$). The error produced by omitting the $(n-k)$ least significant columns and rounding the final result to n bits is estimated, and this estimate (named Correction Value) is added along with the $(n+k)$ most significant columns to produce the rounded product:

\[
\hat{Z}_{trunc} = \frac{\left[(Z_{trunc} + C)\cdot 2^n \right]}{2^n}
\]

The total errors of Truncated Fixed-Width Multipliers come from two operations: reduction and rounding:
\[
E_{total} = E_{red} + E_{rnd} = \hat{Z}_{trunc} - Z
\]
The reduction error $E_{red}$ is:
\[
E_{red} = (Z_{trunc} + C) - Z
\]
As shown, $E_{red}$ depends on how well we estimate the truncated columns. The rounding error $E_{rnd}$ is:
\[
E_{rnd} = \hat{Z}_{trunc} - (Z_{trunc} + C)
\]

Various methods have been developed to find C that reduce the errors due to the truncation and rounding operations.
\subsection{Non-Correction Truncation}
Non-Correction Truncation is the simplest method because it does not use any Correction Value to compensate errors. In the other word, $C = 0$ for every inputs:
\[
\hat{Z}_{0} = \frac{\left[(Z_{trunc})\cdot 2^n \right]}{2^n}
\]

As a result, this is the best in term of area, power dissipation and delay but is the worst in term of errors. And the worst of the worst, the maximum absolute errors (MAE), happens when all the PPs in truncated part is $1$, $\pi_n = 0, \pi_{n+1} = 1, \pi_{n+2}..\pi_{n+k} = 0..0$. Figure \ref{fig:8x8nocorr} shows an examples with $n = 8, k = 2$. 

\[
MAE = \max {|E|} = \frac{2^{-n}}{2} + \sum^{n+k<i+j\le 2n} 2^{-i-j} 
\]

It is worth to notice here that even with the Non-Correction Truncation, if we choose $k$ such that $(n-k)$ small enough, the MAE is still smaller than $1ulp$, which is acceptable in most applications. For example, with $n = 8, k = 6$, we have:
\[
MAE = 2^{-9} + 2\cdot 2^{-15} + 2^{-16} < 2^{-8} = ulp
\]  
\begin{figure}[hbtp]
\centering
\includegraphics[width=\columnwidth]{imgs/8x8nocorr.PNG}
\caption{Non-Correction Method Worst Case}
\label{fig:8x8nocorr}
\end{figure}

\subsection{Correction Constant Truncation}
The interest in Fixed-Width Truncated Multipliers was motivated by Lim's landmark paper in 1992 \cite{lim:1992}. In the paper, a simple but effective way to find Correction Value (which he named Fixed Bias Correction) by analyzing errors statistically proposed. 

To do so, each of PPs $a_i \cdot b_j$ is regarded as a random variable with identical independent distribution (i.i.d). Moreover, probability of $a_i$ or $b_j$ having the value $1$ is assumed $1/2$. As a result, the probability of each PP $a_i\cdot b_j$ having the value $1$ is $1/4$. Hence, the expected value of $a_i\cdot b_j$ is also $1/4$. The Correction Value is now chosen as the expected value of the truncated part as following:

\begin{align*}
C_L   &= E \left\lbrace Z - Z_{trunc} \right\rbrace\\
	&= E \left\lbrace  \sum^{n+k<i+j\le 2n} {(a_i\cdot b_j) 2^{-i-j}} \right\rbrace \\
\end{align*}

Because each of PPs $a_i \cdot b_j$ is i.i.d:
\begin{align*}
C_L &= \sum^{n+k<i+j\le 2n} E \left\lbrace a_i \cdot b_j \right\rbrace 2^{-i-j} \\
  &= \sum^{n+k<i+j\le 2n} \frac{1}{4} \cdot  2^{-i-j} \\
\end{align*}
Taking into account that the column $m$ with $m > n+k$ has $(2n+1-m)$ PPs, we have:
\begin{align*}
C_L  &= \frac{1}{4} \sum_{m=n+k+1}^{2n} ({\sum^{i+j=m} 1}) 2^{-m}\\
   &= \frac{1}{4} \sum_{m=n+k+1}^{2n} (2n+1-m) 2^{-m}\\
\end{align*}
Factoring out $2^{-n}$ from above equation ($u = m - n$), we have:
\begin{align*}
C_L  &= \frac{1}{4} \cdot 2^{-n} \sum_{u=k+1}^{n} (n+1-u) 2^{-u}\\
\end{align*}

It is not hard to see that, with Lim's method:
\[
E\left\lbrace E_{red} \right\rbrace = E \left\lbrace (Z_{trunc} + C) - Z\right\rbrace = 0
\]

Basically, Lim's method is better than Non-Correction Truncation method in terms of errors because it compensates reduction error by adding a Correction Value. However, as mentioned in previous section, besides of reduction error, Truncated Fixed-Width Multipliers also needs to compensate for the rounding errors. 

Based on Lim's work, Schulte and Swartzlander \cite{king:1997} proposed another CCT method that takes into account both reduction and rounding errors. In detail, Correction Value is chosen as the sum of expected value of the truncated part and the rounded part, as following:

\[
C_{SS} = E \left\lbrace Z - Z_{trunc} \right\rbrace + E \left\lbrace Z_{trunc} - \hat{Z}_{0} \right\rbrace
\]
The first part of $C_{SS}$ is nothing but $C_L$, Lim's Correction Value. To compute the second part, authors assumed that each of the production bits $\pi_t$ of $Z_{trunc}$, with $(n+1\le t \le n+k)$ (rounded bits), is independent random variable and the probability of $\pi_t$ having value 1 is 1/2. Figure \ref{fig:8x8schulte} shows an example of 8 bits multipliers. 

\begin{figure}[hbtp]
\centering
\includegraphics[width=\columnwidth]{imgs/8x8king.PNG}
\caption{Schulte's estimation of truncated part and rounded part}
\label{fig:8x8schulte}
\end{figure}
Based on this assumption:
\begin{align*}
E \left\lbrace Z_{trunc} - \hat{Z}_{0} \right\rbrace &= E \left\lbrace \pi_{n+1}\pi_{n+2}..\pi_{n+k} \right\rbrace\\
&= \sum_{t=n+1}^{n+k} \frac{1}{2} \cdot 2^{-t}\\
&= (2^k - 1) \cdot 2^{-n-k-1}\\
\end{align*}
Hence,
\begin{align*}
C_{SS} &= C_L + (2^k - 1) \cdot 2^{-n-k-1}
\end{align*}
The authors also suggested that any Correction Value should be rounded to $(n+k)$ bits (the number of remained columns) as following:
\[
\hat{C}_{SS} = \frac{\left[C_{SS} \cdot 2^{n+k}\right]}{2^{n+k}}
\]

Compensating both types of errors, Schulte and Swartzlander' method is better than Lim's method at no expense.
\subsection{Variable Correction Truncation}
In previous contribution, Correction Value C is a constant and  independent from data (inputs). This approach, in one hand, make the logic simple, but in the other hand, can not utilize the relationship between a specific input and its error. That is the spot where Variable Correction Truncation methods come to the scene. 

Generally, VCT methods use a small set bits of truncated part to improve the estimation of error. As far as the author's knowledge, all VCT methods utilize the column $(n+k+1)$ as the input for prediction (it is the leftmost column in the truncated part). Then, the Correction Value is the function of PPs in the column $(n+k+1)$:
\[
C_{VCT} = f (\left\lbrace a_i \cdot b_j | i+j = n+k+1 \right\rbrace)
\]

In 1998, King and Swartzlander\cite{king:1997} proposed a method named Data-Dependent Truncation. In this method, to compensate for reduction error, the algorithm counts the number of ONE in column $(n+k+1)$ (named $N1$) and add this number to column $(n+k)$. To compensate for the rounding error, the same value as in Schulte and Swartzlander's method is used. These two estimation then are added up together to form the total Correction Value, as following:
\[
C_{K} = N1\cdot 2^{-n-k} + (2^k - 1) \cdot 2^{-n-k-1}
\]
Every Correction Values are then also rounded to $(n+k)$ bits:
\[
\hat{C}_{K} = \frac{\left[C_{K} \cdot 2^{n+k}\right]}{2^{n+k}}
\]

In \cite{stine:2003}, Stine and Duverne proposed a new method named Hybrid Truncated Multipliers, in which, combines both the constant and variable correction methods. They introduced a new parameter p, which represents the percentage of variable correction to use for the correction. The calculation of the number of variable correction bits is the following utilizing the number of bits used in the variable correction method, $N_{variable}$:

\[
N_{hybrid} = floor( N_{variable} \cdot p )
\]

Hybrid method still uses a correction constant to compensate for the rounding error. However, a new correction constant based on the difference between the new varibale correction constant and the constant correction constant, as following:
\[
C_{VCT'} = 2^{-2n-k-2} \cdot N_{hybrid}
\]
\[
C_{round} = \Biggl\lfloor C_{CCT} - C_{VCT'} \Biggr\rfloor_{(n+k)}
\]

In \cite{petra:2010}\cite{decaro:2013}, authors use optimization approach and numerical method to truncated multipliers. The correction value is considered as a function of the $(n+k+1)^{th}$ column (which is named IC - input correction vector). The authors used direct search to find the optimal points. However, as above methods, the authors also assumed that the input distribution is uniform.

\section{Experimental Results}

\section{Proposal}
\subsection{Minimax Truncated Multipliers}

\subsection{Preliminary Results}

% needed in second column of first page if using \IEEEpubid
%\IEEEpubidadjcol


% An example of a floating figure using the graphicx package.
% Note that \label must occur AFTER (or within) \caption.
% For figures, \caption should occur after the \includegraphics.
% Note that IEEEtran v1.7 and later has special internal code that
% is designed to preserve the operation of \label within \caption
% even when the captionsoff option is in effect. However, because
% of issues like this, it may be the safest practice to put all your
% \label just after \caption rather than within \caption{}.
%
% Reminder: the "draftcls" or "draftclsnofoot", not "draft", class
% option should be used if it is desired that the figures are to be
% displayed while in draft mode.
%
%\begin{figure}[!t]
%\centering
%\includegraphics[width=2.5in]{myfigure}
% where an .eps filename suffix will be assumed under latex, 
% and a .pdf suffix will be assumed for pdflatex; or what has been declared
% via \DeclareGraphicsExtensions.
%\caption{Simulation Results.}
%\label{fig_sim}
%\end{figure}

% Note that IEEE typically puts floats only at the top, even when this
% results in a large percentage of a column being occupied by floats.
% However, the Computer Society has been known to put floats at the bottom.


% An example of a double column floating figure using two subfigures.
% (The subfig.sty package must be loaded for this to work.)
% The subfigure \label commands are set within each subfloat command,
% and the \label for the overall figure must come after \caption.
% \hfil is used as a separator to get equal spacing.
% Watch out that the combined width of all the subfigures on a 
% line do not exceed the text width or a line break will occur.
%
%\begin{figure*}[!t]
%\centering
%\subfloat[Case I]{\includegraphics[width=2.5in]{box}%
%\label{fig_first_case}}
%\hfil
%\subfloat[Case II]{\includegraphics[width=2.5in]{box}%
%\label{fig_second_case}}
%\caption{Simulation results.}
%\label{fig_sim}
%\end{figure*}
%
% Note that often IEEE papers with subfigures do not employ subfigure
% captions (using the optional argument to \subfloat[]), but instead will
% reference/describe all of them (a), (b), etc., within the main caption.


% An example of a floating table. Note that, for IEEE style tables, the 
% \caption command should come BEFORE the table. Table text will default to
% \footnotesize as IEEE normally uses this smaller font for tables.
% The \label must come after \caption as always.
%
%\begin{table}[!t]
%% increase table row spacing, adjust to taste
%\renewcommand{\arraystretch}{1.3}
% if using array.sty, it might be a good idea to tweak the value of
% \extrarowheight as needed to properly center the text within the cells
%\caption{An Example of a Table}
%\label{table_example}
%\centering
%% Some packages, such as MDW tools, offer better commands for making tables
%% than the plain LaTeX2e tabular which is used here.
%\begin{tabular}{|c||c|}
%\hline
%One & Two\\
%\hline
%Three & Four\\
%\hline
%\end{tabular}
%\end{table}


% Note that IEEE does not put floats in the very first column - or typically
% anywhere on the first page for that matter. Also, in-text middle ("here")
% positioning is not used. Most IEEE journals use top floats exclusively.
% However, Computer Society journals sometimes do use bottom floats - bear
% this in mind when choosing appropriate optional arguments for the
% figure/table environments.
% Note that, LaTeX2e, unlike IEEE journals, places footnotes above bottom
% floats. This can be corrected via the \fnbelowfloat command of the
% stfloats package.



\section{Conclusion and Future Works}
The conclusion goes here.





% if have a single appendix:
%\appendix[Proof of the Zonklar Equations]
% or
%\appendix  % for no appendix heading
% do not use \section anymore after \appendix, only \section*
% is possibly needed

% use appendices with more than one appendix
% then use \section to start each appendix
% you must declare a \section before using any
% \subsection or using \label (\appendices by itself
% starts a section numbered zero.)
%


%\appendices
%\section{Proof of the First Zonklar Equation}
%Appendix one text goes here.
%
%% you can choose not to have a title for an appendix
%% if you want by leaving the argument blank
%\section{}
%Appendix two text goes here.


% use section* for acknowledgement
\ifCLASSOPTIONcompsoc
  % The Computer Society usually uses the plural form
  \section*{Acknowledgments}
\else
  % regular IEEE prefers the singular form
  \section*{Acknowledgment}
\fi


I would like to thank my advisor, Dr. James Stine, for his great support not only in completing this report but also in my research. I also would like to thank Dr. Keith Teague, Dr. Damon Chandler and Dr. R. Russel Rhinehart for being my committees and giving me great advice to improve my report.


% Can use something like this to put references on a page
% by themselves when using endfloat and the captionsoff option.
\ifCLASSOPTIONcaptionsoff
  \newpage
\fi



% trigger a \newpage just before the given reference
% number - used to balance the columns on the last page
% adjust value as needed - may need to be readjusted if
% the document is modified later
%\IEEEtriggeratref{8}
% The "triggered" command can be changed if desired:
%\IEEEtriggercmd{\enlargethispage{-5in}}

% references section

% can use a bibliography generated by BibTeX as a .bbl file
% BibTeX documentation can be easily obtained at:
% http://www.ctan.org/tex-archive/biblio/bibtex/contrib/doc/
% The IEEEtran BibTeX style support page is at:
% http://www.michaelshell.org/tex/ieeetran/bibtex/
\bibliographystyle{unsrt}
% argument is your BibTeX string definitions and bibliography database(s)
%\bibliography{IEEEabrv,../bib/paper}
%
% <OR> manually copy in the resultant .bbl file
% set second argument of \begin to the number of references
% (used to reserve space for the reference number labels box)
\bibliography{trunc_mult}
%\begin{thebibliography}{1}
%
%\bibitem{IEEEhowto:kopka}
%H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus
%  0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999.
%
%\end{thebibliography}

% biography section
% 
% If you have an EPS/PDF photo (graphicx package needed) extra braces are
% needed around the contents of the optional argument to biography to prevent
% the LaTeX parser from getting confused when it sees the complicated
% \includegraphics command within an optional argument. (You could create
% your own custom macro containing the \includegraphics command to make things
% simpler here.)
%\begin{IEEEbiography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{mshell}}]{Michael Shell}
% or if you just want to reserve a space for a photo:

%\begin{IEEEbiography}{Tuan Nguyen}
%Somethings about me
%\end{IEEEbiography}



% You can push biographies down or up by placing
% a \vfill before or after them. The appropriate
% use of \vfill depends on what kind of text is
% on the last page and whether or not the columns
% are being equalized.

%\vfill

% Can be used to pull up biographies so that the bottom of the last one
% is flush with the other column.
%\enlargethispage{-5in}



% that's all folks
\end{document}


